﻿// 10084.  最小圈.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


/*
https://loj.ac/p/10084

题目描述
原题来自：HNOI 2009

考虑带权的有向图 G=(V,E) 以及 w:E\to R，每条边 e=(i,j)(i\not =j,i\in V,j\in V) 的权值定义为 w_{i,j}，
令 n=|V|。c=(c_1,c_2,\cdots ,c_k)(c_i\in V) 是 G 中的一个圈当且仅当 (c_i,c_{i+1})(1<= i>= k) 和 (c_k,c_1) 都在 E 中，
这时称 k 为圈 c 的长度。同时令 c_{k+1}=c_1，并定义圈 c=(c_1,c_2,\cdots ,c_k) 的平均值为：



\mu (c)=\frac{1}{k}\sum_{i=1}^k w_{c_i,c_{i+1}}
即 c 上所有边的权值的平均值。

令 \mu^*(c)=\min \{\mu (c)\} 为 G 中所有圈 c 的平均值的最小值。
现在的目标是：在给定了一个图 G=(V,E) 以及 w:E\to R 之后，请求出 G 中所有圈 c 的平均值的最小值 \mu ^* (c)=\min \{ \mu (c)\}。

输入格式
第一行包含两个正整数 n 和 m，并用一个空格隔开，其中 n=|V|,m=|E|，分别表示图中有 n 个顶点和 m 条边；

接下来 m 行，每行包含用空格隔开的三个数 i,j,w_{i,j}，表示有一条边 (i,j) 且该边的权值为 w_{i,j}。

输入数据保证图 G=(V,E) 连通，存在圈且有一个点能到达其他所有点。

输出格式
仅包含一个实数 u^*= min{ u(c)}，要求输出到小数点后 8 位。


4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3


3.66666667


2 2
1 2 -2.9
2 1 -3.1

-3.00000000


数据范围与提示
对于 20\% 的数据，1<= n<= 100,1<= m<= 1000；
对于 40\% 的数据，1<= n<= 1000,1<= m<= 5000；
对于 100\% 的数据，1<= n<= 3000,1<= m<= 10^4,|w_{i,j}|<= 10^7。

输入保证 1<= i,j<= n。
*/
int main()
{
    std::cout << "Hello World!\n";
}
 